package homework1_array.alg_68;

import static homework1_array.Utils.printList;

public class ArrayHomework {

    public static void main(String[] args) {

        //todo 作业1：完成这个测试方法中的addByElementBySequence()方法
        arrayAddTest();

        // todo 作业2：完成这个测试类中的removeByElement()方法
        deleteTest();

    }

    /**
     * 在有序列表中插入元素
     */
    private static void arrayAddTest() {

        int[] arr = new int[20];
        arr[0] = 3;
        arr[1] = 4;
        arr[2] = 7;
        arr[3] = 8;
// 1.中间位置插入
        addByElementSequence(arr, 4, 6);
        printList("在有序数组的中间部分插入元素后的结果为：", arr, 5);
        //此时应输出 3 4 6 7 8

//2.尾部插入
        addByElementSequence(arr, 5, 9);
        printList("在有序数组的尾部插入元素后的结果为：", arr, 6);
        //此时应输出 3 4 6 7 8 9

//3.数组首部插入
        addByElementSequence(arr, 6, 1);
        printList("在有序数组的首部部分插入元素后的结果为：", arr, 7);
        //此时应输出：1 3 4 6 7 8 9

    }

    //todo 作业1：完成这个方法

    /**
     * @param arr       存储元素的数组
     * @param size      数组中已经存储的元素数量
     * @param element   要插入数组的新元素
     * @return
     */
    public static void addByElementSequence(int[] arr, int size, int element) {
        // 此处的index既充当标志位的作用，也充当下标的作用
        int index = -1;

        // arrayAddTest()方法中的逻辑是在进行添加元素操作时，就把添加后的size给定了
        // 所以此处应设的条件为size > arr.length
        if (size > arr.length) {
            throw new IllegalArgumentException("Add failed. Array is full.");
        }

        for (int i = 0; i < size; i++) {
            // 此处假设数组中不允许存在值重复的元素，所以条件为arr[i] > element
            if (arr[i] > element) {
                // 若数组中下标为i的元素值比待插入的元素值大
                // 则该位置就是新元素可以插入的位置
                index = i;
                // 找到第一个满足插入条件的位置事即退出
                break;
            }
        }

        if (index != -1) {
            // 注意，数组插入前最后一个元素的下标是size - 1
            for (int i = size - 1; index <= i; i--) {
                arr[i + 1] = arr[i];
            }
            arr[index] = element;
        } else {
            // 若数组中所有已存储的元素都比待插入的元素值小，则直接将该元素插入到最后一个元素之后
            arr[size] = element;
        }

        // 只要插入成功，应将size值加1，此处虽然无法返回size的值，但应保留逻辑
        size++;
    }

    /**
     * 删除测试
     */
    private static void deleteTest() {
        int[] arr = new int[]{2, 3, 4, 9, 10, 11, 12};

//1.删除头元素
        removeByElement(arr, 7, 2);
        printList("删除头元素后的结果为：", arr, 6);
        //此时应该打印 3 4 9 10 11 12

//2. 删除尾元素
        removeByElement(arr, 6, 12);
        printList("删除尾元素的结果为：", arr, 5);
        //此时应该打印 3 4 9 10 11

//3. 删除中间元素：
        removeByElement(arr, 5, 9);
        printList("删除中间元素的结果为：", arr, 4);
        //此时应该打印 3 4 10 11
    }

    /**
     * 从数组中删除元素e
     *
     * @param arr   存储元素的数组
     * @param size  数组已经存放的元素大小
     * @param key   要删除的元素
     */
    public static void removeByElement(int[] arr, int size, int key) {
        int index  = -1;

        for (int i = 0; i < size; i++) {
            if (arr[i] == key) {
                index = i;
                break;
            }
        }

        if (index != -1) {
            for (int i = index + 1; i < size; i++) {
                arr[i - 1] = arr[i];
                // 之所以不用arr[i] = arr[i + 1]，是为了防止下标越界
            }
        }

        size--;
    }
}
